package com.lun.medium;

import com.lun.util.BinaryTree.TreeNode;

public class InsertIntoABinarySearchTree {
    //方法一：递归法
	public TreeNode insertIntoBST(TreeNode root, int val) {
		if(root == null)
			return new TreeNode(val);
    	
    	if(val < root.val) {
    		root.left = insertIntoBST(root.left, val);
    	}else if(root.val < val){
    		root.right = insertIntoBST(root.right, val);
    	}
    	
    	return root;
    }
    
	//方法二：迭代法
    public TreeNode insertIntoBST2(TreeNode root, int val) {
    	if(root == null)
    		return new TreeNode(val);
    	
    	TreeNode curr = root;
    	
    	while(true) {
    		 if(val < curr.val) {
    			 if(curr.left != null) {
    				 curr = curr.left;
    			 }else {
    				 curr.left = new TreeNode(val);
    				 break;
    			 }
    		 }else if(curr.val < val) {
    			 if(curr.right != null) {
    				 curr = curr.right;
    			 }else {
    				 curr.right = new TreeNode(val);
    				 break;
    			 }
    		 }
    	}
    	
    	return root;
    }
}
